#include <stdio.h>

/* https://c.biancheng.net/view/prim.html */

// 记录图中顶点的个数
#define V 6
/*定义一个INF表示无穷大*/
#define INF 2147483647
typedef enum {false, true} bool;

//顶点的最大个数
#define MAX_VERtEX_NUM 20
//表示顶点之间的关系的变量类型
#define VRType int
//存储弧或者边额外信息的指针变量类型
#define InfoType char
//图中顶点的数据类型
#define VertexType int

typedef struct {
    //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值
    VRType adj;
    //弧或边额外含有的信息指针
    InfoType * info;
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    //存储图中顶点数据
    VertexType vexs[MAX_VERtEX_NUM];
    //二维数组，记录顶点之间的关系
    AdjMatrix arcs;
    //记录图的顶点数和弧（边）数
    int arcnum, vexnum;
}MGraph;

//查找权值最小的、尚未被选择的顶点，key 数组记录了各顶点之间的权值数据，visited数组记录着各个顶点是否已经被选择的信息
int min_key(int key[], bool visited[]) {
    //遍历 key 数组使用，min 记录最小的权值，min_index 记录最小权值关联的顶点
    int min = INF;
    int min_index;
    //遍历 key 数组
    for(int v = 0; v < V; v++) {
        //如果当前顶点未被选择，且对应的权值小于 min 值
        if(visited[v] == false && key[v] < min) {
            //更新  min 的值并记录该顶点的位置
            min = key[v];
            min_index = v;
        }
    }
    //返回最小权值的顶点的位置
    return min_index;
}

//输出最小生成树
void print_MST(int parent[], int cost[V][V]) {
    int minCost = 0;
    printf("最小生成树为：\n");
    //遍历 parent 数组
    for(int i = 1; i < V; i++) {
        //parent 数组下标值表示各个顶点，各个下标对应的值为该顶点的父节点
        //由于数组下标从 0 开始，因此输出时各自 +1
        printf("%d - %d weight:%d\n", parent[i] + 1, i + 1, cost[i][parent[i]]);
        //统计最小生成树的总权值
        minCost += cost[i][parent[i]];
    }
    printf("总权重值为：%d\n", minCost);
}

//根据用户提供了图的信息（存储在 cost 数组中），寻找最小生成树
void findMST(int cost[V][V]) {
    //key 数组用于记录 B 类顶点到 A 类顶点的权值
    //parent 数组用于记录最小生成树中各个顶点父节点的位置，便于最终生成最小生成树
    //visited 数组用于记录各个顶点属于 A 类还是 B 类
    int parent[V], key[V];
    bool visited[V];

    // 初始化 3 个数组
    for(int i = 0; i < V; i++) {
        // 将 key 数组各个位置设置为无限大的数
        key[i] = INF;
        // 所有的顶点全部属于 B 类
        visited[i] = false;
        // 所有顶点都没有父节点
        parent[i] = -1;
    }
    // 选择 key 数组中第一个顶点，开始寻找最小生成树
    // 该顶点对应的权值设为 0
    key[0] = 0;
    // 该顶点没有父节点
    parent[0] = -1;

    // 对于 V 个顶点的图，需选择 V-1 条路径，即可构成最小生成树
    for(int x = 0; x < V - 1; x++) {
        // 从 key 数组中找到权值最小的顶点所在的位置
        int u = min_key(key, visited);
        // 该顶点划分到 A 类
        visited[u] = true;

        // 由于新顶点加入 A 类，因此需要更新 key 数组中的数据
        for(int v = 0; v < V; v++) {
            // 如果B类中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小，表明新顶点的加入，使得B类到A类 顶点的权值有了更好的选择
            if(cost[u][v] !=0 && visited[v] == false && cost[u][v] < key[v]) {
                // 更新 parent 数组记录的各个顶点父节点的信息
                parent[v] = u;
                // 更新 key 数组
                key[v] = cost[u][v];
            }
        }
    }
    //根据 parent 记录的各个顶点父节点的信息，输出寻找到的最小生成树
    print_MST(parent, cost);
}

//构造无向网
void CreateUDN1(int array[][V]) {
    //在二维数组中添加弧的数据
    /*
    {
         A  B  C  D  S  T
    A    0  6  3  ∞  7  ∞
    B    6  0  4  2  ∞  5
    C    3  4  0  3  8  ∞
    D    ∞  2  3  0  ∞  2
    S    7  ∞  8  ∞  0  ∞
    T    ∞  5  ∞  2  ∞  0
    }
    */
   //无向图的二阶矩阵沿主对角线对称
   //A-B
   array[1][0] = 6;
   array[0][1] = 6;
   //A-C
   array[0][2] = 3;
   array[2][0] = 3;
   //B-C
   array[1][2] = 4;
   array[2][1] = 4;
   //B-D
   array[1][3] = 2;
   array[3][1] = 2;
   //B-T
   array[1][5] = 5;
   array[5][1] = 5;
   //C-D
   array[2][3] = 3;
   array[3][2] = 3;
   //C-S
   array[2][4] = 8;
   array[4][2] = 8;
   //D-T
   array[3][5] = 2;
   array[5][3] = 2;
   //S-A
   array[4][0] = 7;
   array[0][4] = 7;
}

int main(int argc, char * argv[]) {
    int cost[V][V] = { 0 };
    //调用创建函数，传入地址参数
    CreateUDN1(cost);
    //输出图的二阶矩阵
    //PrintGraph(G);
    printf("\n");
    // 根据图的信息，寻找最小生成树
    findMST(cost);
    return 0;
}